package 剑指offer;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @description: 有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，
 * MedianHolder可以随时取得之前吐出所有数的中位数。
 * [要求]
 * 1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
 * 2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)
 * <p>
 * 每行有一个整数opt表示操作类型
 * 若opt=1，则接下来有一个整数N表示将N加入到结构中。
 * 若opt=2，则表示询问当前所有数的中位数
 * @author: ywk
 * @date: 2020-11-07
 */
public class 随时找到数据流的中位数 {
    public static void main(String[] args) {
        System.out.println(flowmedian1(new int[][]{{1, 5}, {2}, {1, 3}, {2}, {1, 6}, {2}, {1, 7}, {2}}));
        System.out.println(flowmedian(new int[][]{{1, 5}, {2}, {1, 3}, {2}, {1, 6}, {2}, {1, 7}, {2}}));
    }

    /**
     * the medians
     *
     * @param operations int整型二维数组 ops
     * @return double浮点型一维数组
     */
    public static double[] flowmedian(int[][] operations) {
        List<Double> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        // write code here
        for (int[] op : operations) {
            if (op.length == 1) {
                //询问
                double v;
                if (list.size() % 2 != 0) {
                    v = list.get(list.size() / 2);
                } else {
                    v = (list.get(list.size() / 2) +
                            list.get(list.size() / 2 - 1)) / 2.0;
                }
                result.add(v);
            } else {
                //添加
                insertNum(list, op[1]);
            }
        }
        double[] arr = new double[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        System.out.println(result);
           return result.stream().mapToDouble(Double::doubleValue).toArray();
    }

    public static void insertNum(List<Integer> list, int a) {
        if (list.size() == 0) {
            list.add(a);
            return;
        }
        int left = 0, right = list.size();
        while (left < right) {
            int mid = (left + right) / 2;
            Integer midVal = list.get(mid);
            if (midVal == a) {
                list.add(mid, a);
                return;
            } else if (midVal < a) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        list.add(left, a);
        System.out.println(list);
    }

    public static double[] flowmedian1 (int[][] operations) {
        ArrayList<Double> arr = new ArrayList<>();
        //保证最大堆永远小于最小堆
        PriorityQueue<Integer> maxheap = new PriorityQueue((Comparator<Integer>) (o1, o2) -> o2 - o1);
        PriorityQueue<Integer> minheap = new PriorityQueue<>(Comparator.comparingInt(o -> o));
        for (int[] op : operations){
            if (op[0] == 1){
                if (maxheap.isEmpty() || maxheap.peek() > op[1]){
                    maxheap.add(op[1]);
                }else{
                    minheap.add(op[1]);
                }
                //高度差维持一
                if (minheap.size() == maxheap.size() + 2){
                    maxheap.add(minheap.poll());
                }
                if (maxheap.size() == minheap.size() + 2){
                    minheap.add(maxheap.poll());
                }
            }else{
                if (maxheap.size() == 0){
                    double ans = -1;
                    arr.add(ans);
                    continue;
                }
                if (maxheap.size() == minheap.size()){
                    double num1 = maxheap.peek();
                    double num2 = minheap.peek();
                    arr.add((num1 + num2) / 2);
                }else{
                    if (maxheap.size() > minheap.size()){
                        double num1 = maxheap.peek();
                        arr.add(num1);
                    }else{
                        double num1 = minheap.peek();
                        arr.add(num1);
                    }
                }
            }
        }
        double[] res = new double[arr.size()];
        for (int i = 0; i < res.length; i++){
            res[i] = arr.get(i);
        }
        System.out.println(arr);
        return res;
    }

}
